//插入排序
//基于当前元素前面的序列是有序的前提，
// 从后往前去寻找当前元素在前面那个序列里的正确位置

// [5, 3, 2, 4, 1]

// [3, 5]

// [2, 3, 5]

// [2, 3, 4, 5]

// [1, 2, 3, 4, 5]

var example = [8, 94, 15, 88, 55, 76, 21, 39];

function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var temp = arr[i];
    var j = i - 1;//默认已排序的元素
    while (j >= 0 && arr[j] > temp) {  //在已排序好的队列中从后向前扫描
      arr[j + 1] = arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr
}
console.log(insertSort(example))